package com.cuz.二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class l662二叉树最大宽度 {
    public static void main(String[] args) {
        //root = [1,3,2,5,3,null,9]
        TreeNode n1 = new TreeNode(1);
        TreeNode n3 = new TreeNode(3);
        TreeNode n2 = new TreeNode(2);
        TreeNode n5 = new TreeNode(5);
        TreeNode n33 = new TreeNode(3);
        TreeNode n9 = new TreeNode(9);
        n1.left = n3;
        n1.right = n2;
        n3.left = n5;
        n3.right = n33;

        n2.right = n9;
        System.out.println(new l662二叉树最大宽度().widthOfBinaryTree(n1));
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        //结果集合
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        //队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        //当前层的节点数量为1
        int curLevelNum = 1;

        while (!queue.isEmpty()) {
            //存储当前层节点的值
            List<Integer> curLevelNodeValList = new ArrayList<>(curLevelNum);
            //下一层节点的数量
            int nextLevelNodeNum = 0;

            //遍历当前层
            while (curLevelNum > 0) {
                TreeNode temp = queue.removeFirst();
                curLevelNodeValList.add(temp.val);

                //处理左右儿子，只要不为null 那么加入并且下一次节点数量加1
                if (temp.left != null) {
                    queue.addLast(temp.left);
                    nextLevelNodeNum++;
                }
                if (temp.right != null) {
                    queue.addLast(temp.right);
                    nextLevelNodeNum++;
                }
                //当前层减少
                curLevelNum--;
            }
            //当前层结束了，到下一层
            curLevelNum = nextLevelNodeNum;
            //存储结果
            res.add(curLevelNodeValList);
        }
        return res;
    }

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        int max = 1;
        while (!queue.isEmpty()) {
            boolean isLeef = true;
            LinkedList<TreeNode> tempList = new LinkedList<>();
            for (int i = 0; i < max && !queue.isEmpty(); i++) {
                TreeNode temp = queue.removeFirst();
                if (temp == null) {
                    continue;
                }
                if (temp.right != null || temp.left != null) {
                    isLeef = false;
                }
                tempList.add(temp.left);
                tempList.add(temp.right);
            }
            if (!isLeef) {
                max = Math.max(tempList.size(), max);
                queue.addAll(tempList);
            } else {
                return max;
            }
        }
        return max;
    }
}
